# @Time    :2025/4/13 14:57
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None


class Hashtable:
    def __init__(self):
        self.__size = 0
        self.__capacity = 2  # 总容量
        self.__load_factor = 0.7  # 加载因子(元素个数/数组容量)
        self.__table = [None] * self.__capacity  # 整个数组部分 存储数据

    def __hash(self, key):
        """计算hash值，找到对应的下标"""
        return hash(key) % self.__capacity

    @property
    def size(self):
        return self.__size

    def is_empty(self):
        return self.__size == 0

    def display(self):
        # 1，对数组元素的遍历
        for i, node in enumerate(self.__table):  # node是链表中存放的头节点
            print(f"索引为{i}：", end="")
            current = node  # 尽量不去操作外层的循环条件
            # 2，对链表节点进行遍历
            while current:
                print(f"({current.key},{current.value})->", end="")
                current = current.next  # 头节点的下一个节点
            print("None")

    def __grow(self):
        """扩容"""
        self.__capacity *= 2
        self.__table, old_table = [None] * self.__capacity, self.__table
        self.__size = 0
        # 把原有的数组的节点一个个取出来
        for node in old_table:
            current = node
            while current:
                self.put(current.key, current.value)
                current.next = current

    def put(self, key, value):
        """向哈希表插入键值对 """
        # 如果超过加载因子就需要扩容
        # if self.__size / self.__capacity > self.__load_factor:
        #     self.__grow()
        # 1,先确定要插入节点的下标位置
        index = self.__hash(key)
        # 2,封装一个节点对象
        new_node = Node(key, value)
        # 3，判断数组下标位置 是否有元素 ，如果没有直 接把当前节点插入，作为头节点
        if self.__table[index] is None:
            self.__table[index] = new_node
        # 4,如果当前节点有数据
        else:
            current = self.__table[index]
            while current:
                if current.key == key:  # 当前节点的Key跟传入的key作比较
                    current.value = value
                    return
                if not current.next:#如果没有下一个节点停止循环，下边代码不再执行，如果有下一个节点就下一个节点指向当前节点，进入下一次循环
                    break
                current = current.next

            current.next = new_node
        self.__size += 1

    def remove(self, key):
        """根据key删除哈希表中元素"""
        # 1,先确定要删除的键值对的下标位置
        index = self.__hash(key)
        current = self.__table[index]  # 当前要删除的元素所在的头 节点
        prev = None  # 上一个节点
        while current:
            if current.key == key:
                if prev:
                    # 如果存在前一个节点，说明这个不是一个头节点
                    prev.next = current.next
                else:
                    # 删除的是头节点
                    self.__table[index] = current.next
                self.__size -= 1
                return True
            prev = current
            current = current.next
        return False

    def get(self, key):
        """根据key，获取对应的Value"""
        index = self.__hash(key)
        current = self.__table[index]  # 当前要删除的元素所在的头 节点
        while current:
            if current.key == key:
                return current.value
            current = current.next
        return None

    def for_each(self, func):
        for node in self.__table:
            current = node
            while current:
                func(current.key, current.value)
                current = current.next


ht = Hashtable()
ht.put(1, 1)
ht.put(2, 3)
ht.put(3, 56)
ht.put(10, 91)  # 粗布来

# ht.remove(3)
print(ht.get(3))
ht.display()
ht.for_each(print)
